While Time Complexity measures the critical dimension of execution speed scaling, algorithmic efficiency is incomplete without addressing memory usage. Space Complexity quantifies the total memory required by an algorithm to run, relative to the input size ($n$).
- We primarily focus on auxiliary space, which is the temporary working memory required by the algorithm, excluding the space taken up by the input array ($A$) and the output array ($B$).
- This distinction determines whether a sorting algorithm can be run efficiently on systems with limited memory:
- In-Place Sorting: Requires auxiliary space that is constant ($O(1)$) or logarithmic ($O(\log n)$). The sort is performed by modifying the array $A$ directly, typically using only a few pointers and temporary swap variables.
- Out-of-Place Sorting: Requires auxiliary space that is linear ($O(n)$). This usually means the algorithm must allocate a temporary array or copy of the input, proportional to the size of $n$, to complete the sorting process.
- Often, there is a Time/Space trade-off: achieving optimal time efficiency (like $O(n \log n)$ in Merge Sort) frequently requires allocating $O(n)$ auxiliary space.
Comparison of Space Complexity Categories
| Category | Auxiliary Space | Characteristics | Examples (Worst-Case Time) |
|---|---|---|---|
| In-Place | $O(1)$ or $O(\log n)$ | Input array $A$ is modified directly. Excellent for memory constraints. | Bubble ($O(n^2)$), Insertion ($O(n^2)$), Quick Sort (Avg: $O(n \log n)$, often $\log n$ space) |
| Out-of-Place | $O(n)$ | Requires a new temporary list proportional to input size $n$. | Merge Sort ($O(n \log n)$ time) |